package java学习.代码随想录.动态规划;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/4 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 最佳买卖股票时机含冷冻期 {

    /**
     * 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
     *
     * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
     *
     * 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown
     *               0 1 2 3 4
     *输入: prices = [1,2,3,0,2]        输出: 3
     * 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
     * dp[i] 前i天 获取的最大利润
     * dp[0] = 0; dp[1] = 1, dp[2] = 1 , dp[3] = 1  dp[4] = 3
     * dp[0] = max(dp[0],0- p[i])
     * dp[1] = max(dp[0],p[i])
             * dp[2] = max(dp[1], p[2]-min(i-1,i))
             * dp[3] = max(dp[2], )
             * dp[4] = 2,  2
       dp[2] =

               dp[1] > dp[0]
           if(dp[i] >dp[i-1]  ){

            dp[2] = dp[1];
            dp[i+1] = dp[i];
               i+=2;
           }
            dp[3] = dp[2]
            dp[i] = dp[i-1];
     * dp[3] = dp[2] = 2;
     * dp[]
     *
     */
    /**
     *   0 1 2 3 4 5
     *  [6,1,3,2,4,7] 输出  6
     *  0 0 2  2
     *
     *   0 1 2 3 4 5 6 7
     *  [3,3,5,0,0,3,1,4]  6

         0 0 2 2 2 5 5

     */
    public static int maxProfit(int[] prices) {
        int n = prices.length;
        int [] dp = new int[n];

        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            dp[i]  = dp[i-1]+prices[i] - Math.min(prices[i],prices[i-1]);
//            dp[i] = Math.max(dp[i-1],prices[i] -Math.min(prices[i],prices[i-1]) );

            if (dp[i] > dp[i-1] && i+2< n ){
                if (i+1 < n){
                    dp[i+1] = dp[i];
                }
                i+=2;
                dp[i] = dp[i-1];
            }

        }
        System.out.println(Arrays.toString(dp));

        int[] dp1 = new int[n];
        int min = prices[0];
        for (int i = 1; i <n; i++) {
            min = Math.min(prices[i],min);
            dp1[i] = Math.max(dp1[i-1],prices[i]- min);

        }
        return Math.max(dp[n-1],dp1[n-1]);
    }

    /**
     * 1. dp[]
     * 状态
     *
     *  0 买入  dp[i][0] =        之前就已买入、      昨天是冷冻期，今天买入、   卖出且冷冻期过后几天，今天买入，
     *         dp[i][0] =     max     dp[i-1][0]    dp[i-1][3]-prices[i]       dp[i-1][1] - prices[i]
     *  1 卖出且过了冷冻期好几天        昨天是冷冻期
     *         dp[i][1] =     max   dp[i-1][3];     dp[i-1][1]
     *  2 今天卖出                 之前就卖出、        昨天买入
     *         dp[i][2] =        dp[i-1][2]       dp[i-1][0]+prices[i]
     *  3 冷冻期                   昨天卖出
     *         dp[i][3] =    dp[i-1][2]
     */
    public static int maxProfit2(int[] prices) {
        int n = prices.length;
        int [] [] dp = new int[n][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;

        for (int i = 1; i <n ; i++) {

            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][0] = Math.max( dp[i][0] ,dp[i-1][3]-prices[i] );

            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3] );

            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][0]+prices[i]);

            dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2] );

        }
        int result = Math.max(dp[n-1][1],dp[n-1][2]);
        int result2 = Math.max(result,dp[n-1][3]);
//        return dp[n-1][2];
        return result2;
    }

    /**
     *                          之前卖出           买入后卖出
     * dp[i][0] 卖出(不持有)      dp[i-1][0]     dp[i-1][1]+p[i]
     *                          之前买入          卖出过了冷冻期后买入
     * dp[i][1] 买入(持有)       dp[i-1][1]     dp[i-1][2] -p[i]  【卖出后不能立即买入：dp[i-1][0]-p[i]】
     *                         卖出后才进入冷冻期
     * dp[i][2] 冷冻期          dp[i-1][0]
     */
    public static int maxProfit3(int[] prices) {
        int n = prices.length;
        int [][] dp = new int[n][3];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        for (int i = 1; i < n; i++) {

            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
//             卖出后不能立即买入， 需要过冷冻期
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2]-prices[i]);
            dp[i][2] = dp[i-1][0];
        }
        return Math.max(dp[n-1][0],dp[n-1][2]);
    }

    public static void main(String[] args) {
//        int [] arr = {1,2,3,0,2};
//        int [] arr = {6,1,3,2,4,7};
        int [] arr = {3,3,5,0,0,3,1,4};
        System.out.println(maxProfit(arr));
    }


    /**
     * 0 无操作
     * 1 买入
     * 2 卖出
     * 3 冷冻期
     * dp[0][1] = -prices[i]
     *
     * dp[i][1] = dp[i-1][3]-p[i]  dp[i-1][1]
     * dp[i][2] = dp[i-1][1]+p[i]  dp[i-1][2]
     * dp[i][3] = dp[i-1][2]
     *
     */
    public static int maxProfit4(int[] prices) {
        int n = prices.length;
        int [][] dp = new int[n][4];
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][1] = Math.max(dp[i-1][3]-prices[i], dp[i-1][1]);
            dp[i][2] = Math.max(dp[i-1][1]+prices[i], dp[i-1][2]);
            dp[i][3] = dp[i-1][2];
        }
     return Math.max(dp[n-1][2],dp[n-1][3]);
    }
}